# -*- coding: utf-8 -*-
# @Time    : 2019/10/17 10:44
# @Author  : LiHaowen
# @Email   : lihaowen2017@163.com
# @File    : dict_performance.py
# dict 和 list 查找性能测试
from random import randint


def load_list_data(total_nums, target_nums):
    """
    从文件中读取数据，以list的方式返回
    :param total_nums: 读取的数量
    :param target_nums: 需要查询的数据的数量
    """
    all_data = []  # 总数据量
    target_data = []  # 查找的元素
    file_name = "G:/慕课网课程/AdvancePython/fbobject_idnew.txt"
    with open(file_name, encoding="utf8", mode="r") as f_open:
        for count, line in enumerate(f_open):
            if count < total_nums:
                all_data.append(line)
            else:
                break

    for x in range(target_nums):  # 从总数据中随机生成的数据
        random_index = randint(0, total_nums)
        if all_data[random_index] not in target_data:
            target_data.append(all_data[random_index])
            if len(target_data) == target_nums:
                break

    return all_data, target_data


def load_dict_data(total_nums, target_nums):
    """
    从文件中读取数据，以dict的方式返回
    :param total_nums: 读取的数量
    :param target_nums: 需要查询的数据的数量
    """
    all_data = {}
    target_data = []
    file_name = "G:/慕课网课程/AdvancePython/fbobject_idnew.txt"
    with open(file_name, encoding="utf8", mode="r") as f_open:
        for count, line in enumerate(f_open):
            if count < total_nums:
                all_data[line] = 0
            else:
                break
    all_data_list = list(all_data)
    for x in range(target_nums):
        random_index = randint(0, total_nums-1)
        if all_data_list[random_index] not in target_data:
            target_data.append(all_data_list[random_index])
            if len(target_data) == target_nums:
                break

    return all_data, target_data


def find_test(all_data, target_data):
    #测试运行时间
    test_times = 100
    total_times = 0
    import time
    for i in range(test_times):
        find = 0
        start_time = time.time()
        for data in target_data:
            if data in all_data:
                find += 1
        last_time = time.time() - start_time
        total_times += last_time
    return total_times/test_times


if __name__ == "__main__":
    all_data, target_data = load_list_data(10000, 1000)
    # all_data, target_data = load_list_data(100000, 1000)
    # all_data, target_data = load_list_data(1000000, 1000)


    # all_data, target_data = load_dict_data(10000, 1000)
    # all_data, target_data = load_dict_data(100000, 1000)
    # all_data, target_data = load_dict_data(1000000, 1000)
    last_time = find_test(all_data, target_data)

    # dict查找性能远远大于list
    # 在list中随着list数据轭增大，查找时间会增大
    # 在dict中查找元素不会随着dict的增大而增大
    print(last_time)
    # 哈希计算偏移量形成哈希表存入数组内存，数组可以直接存取，不需要遍历
    # 哈希冲突解决方法
    # "abc" -> ("c" + 随机数) -> hash
    # 还冲突
    # "abc" -> ("bc" + 随机数) -> hash  # 往前加一位 计算散列值
    # 去重时首选set

    # dict的key或者set的值都必须是可hash的
    # 不可变的对象都是可hash的， __str__, fronzenset, tuple, 自己实现的类 __hash__
    # dict 的内存花销大，但是查询速度快，自己定义的对象 或者python内存的对象都是用dict包装的
    # dict存储顺序与元素添加顺序有关  python 内部实现了order_dict，尽量不要期望dict的顺序性
    # 添加顺序可能改变已有数据的顺序，重新申请内存空间的时候改变数据映射顺序。
